\documentclass[11pt, a4paper]{article}

% Configuración de márgenes de las páginas
	\usepackage{a4wide}

% Paquete de acentos para Linux
	\usepackage[utf8]{inputenc}

% Paquete para reconocer la separación en sílabas en español
	\usepackage[spanish]{babel}

% Paquetes especiales para el TP
	\usepackage{./otros/caratula}
	\usepackage{pdfpages}

% Paquete para incluir hypervinculos
	\usepackage{color}
	\usepackage{url}
	\definecolor{lnk}{rgb}{0,0,0.4}
	\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

% Paquete para armar índices
	\usepackage{makeidx}
	\makeindex

% Más espacio entre líneas
	\parskip=1.5pt

% Opciones de enumerates
	\usepackage{enumerate}

% Para que las tablas no se muevan libremente
	\usepackage{float}
	\restylefloat{table}

\newcommand{\slambda}{Sarsa-$\lambda$ }

\begin{document}

% Carátula
	\titulo{Aprendizaje por Refuerzos}
	\fecha{2012}
	\materia{Aprendizaje por Refuerzos}
	\integrante{De Sousa Mariano}{389/08}{marian\_sabianaa@hotmail.com}
	\integrante{Mariano Bianchi}{92/08}{marianobianchi08@gmail.com}
	\integrante{Pablo Brusco}{527/08}{pablo.brusco@gmail.com}
	\maketitle

\section{Problema}
Para este trabajo, se utilizo una versi\'on simplificada del Tower Blocks, el cual se basa en un edificio de bloques al que hay que agregarle nuevos pisos utilizando una gr\'ua. La dificultad radica en que el jugador no puede manejar la gr\'ua, solo puede ejecutar la acci\'on de soltar un nuevo piso sobre el edificio ya construido. De acuerdo a la presici\'on con que se deposite el piso, la torre gana o pierde estabilidad. 
\begin{center} \includegraphics[scale=0.50]{towerblocks}\end{center}

Ya que el juego tiene una gran variedad de niveles, se opto por un modelo simple en el cual tenemos que agregar pisos (bloques) a un edificio intentando llegar a una cierta cantidad y sin haber hecho que se derrumbe. Para ello existe una gr\'ua que se mueve de manera \textbf{constante} sobre el edificio y nos permite ejecutar la acci\'on de tirar o no tirar.

\section{Ambiente}
En esta etapa se implementaron todos los objetos necesarios para que el ambiente sea lo más similar al juego real. Estos objetos son:

\begin{itemize}
\item Una grúa que tiene un movimiento lineal entre dos posiciones (en este caso -49 y +49), a velocidad constante (1). Se mueve en ambas direcciones (izquierda y derecha). Es la encargada de sostener los pisos que se van a ir agregando al edificio. El agente le dará la orden de sostener o tirar el piso en un momento dado. 

\item Un edificio que posee un movimiento pendular que va variando en velocidad de acuerdo a que tan desbalanceado est\'a. El desbalanceo está dado por que tan cerca o lejos del centro del edificio fueron cayendo los pisos arrojados por el agente desde la grúa. Por la forma en que lo modelamos, cuanto más alto sea el edificio, mayor estabilidad tendrá y por lo tanto será más difícil que se derrumbe.
\end{itemize}

El ambiente, mantiene un estado visible para el exterior que contiene la posici\'on y velocidad de la torre y adem\'as, la posici\'on y direcci\'on de la gr\'ua. 

Dados los parametros que mantiene el ambiente, la cantidad de estados est\'a dada por:
$$ \#estados = \#posiciones\_grua * \#direcciones\_grua * \#posiciones\_torre *  \#velocidades\_torre  $$
Que dada la configuraci\'on que se utilizo, serian:
$$ \# estados = 99 * 2 * 99 * 11 = 215622 $$

Aunque no todos ellos son alcanzables dependiendo de otro factor. Este otro factor es el \'angulo m\'aximo que se admite que tenga la torre antes de colapsar y que fuimos variando para encontrar buena dinamica, dejandolo en 30 grados. 

\section{Agentes}
Para implementar los jugadores, utilizamos 2 tipos de agentes. Un agente que aprende utilizando la tecnica de Q-Learning y otro que aprende usando el algoritmo \slambda (ambos utilizando los algoritmos vistos en clase).

Estos agentes, reciben est\'imulos seg\'un sus posibles acciones: 
\begin{itemize}
\item Tirar
\item Pasar
\end{itemize}
En donde el ambiente puede responder con distintos refuerzos que contemplaban los siguientes casos:
\begin{itemize}
\item Refuerzo por pasar (negativo chico)
\item Refuerzo por tirar y no golpear a la torre (negativo medio)
\item Refuerzo por pegarle a la torre y lograr que se caiga (negativo grande)
\item Refuerzo por tiro  exitoso (golpe\'o la torre y se agreg\'o un nuevo piso)
\end{itemize}

\newpage

\subsection{Experimentos}

Para responder a las distintas preguntas que uno se puede plantear con respecto a los algoritmos y sus par\'ametros, corrimos los siguientes experimentos, siempre el objetivo era llegar a los 20 pisos

\bigskip

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | c| }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ & Pisos desde \\
  \hline 
 	 Q-Learning  & 0.001  & 0.8  & 0.7 & 1 \\
	Q-Learning  & 0.001  & 0.8  & 0.7 &  10\\
	Q-Learning  & 0.001  & 0.8  & 0.7 &  20 \\
	Q-Learning  & 0.001  & 0.8  & 0.7 &  30\\
	Q-Learning  & 0.001  & 0.8  & 0.7 &  50\\
	Q-Learning  & 0.001  & 0.8  & 0.7 &  70\\
  \hline

\end{tabular}
\caption {Distintas estabilidades en Q-Learning}
\end{table}

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | c | c | }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ & $\lambda$ & Pisos desde \\
  \hline 
 	 \slambda  & 0.001  & 0.8  & 0.7 & 0.3 & 1 \\
	\slambda  & 0.001  & 0.8  & 0.7 &  0.3& 10 \\
	\slambda  & 0.001  & 0.8  & 0.7 &  0.3& 20  \\
	\slambda  & 0.001  & 0.8  & 0.7 &  0.3& 30 \\
	\slambda  & 0.001  & 0.8  & 0.7 &  0.3& 50 \\
	\slambda  & 0.001  & 0.8  & 0.7 &  0.3& 70 \\
  \hline

\end{tabular}
\caption {Distintas estabilidades en \slambda}
\end{table}

Luego de estos experimentos fijamos el piso desde el cual se comienza en 50.

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | c| }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ & $\lambda$ \\
  \hline 
 	 Q-Learning  & 0.001  & 0.8  & 0.7 & - \\
	\slambda & 0.001  & 0.8  & 0.7 & 0.001 \\
	\slambda & 0.001  & 0.8  & 0.7 & 0.3 \\
	\slambda  & 0.001  & 0.8  & 0.7 & 0.7\\
  \hline

\end{tabular}
\caption {Qlearning vs \slambda}
\end{table}

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ \\
  \hline 
 	 Q-Learning  & 0  & 0.8  & 0.7 \\
	 Q-Learning  & 0.0001  & 0.8  & 0.7 \\
	 Q-Learning  & 0.001  & 0.8  & 0.7 \\
	 Q-Learning  & 0.01  & 0.8  & 0.7 \\
  \hline
\end{tabular}
\caption {Epsilons en Qlearning}
\end{table}

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ \\
  \hline 
 	 Q-Learning  & 0.001  & 0.8  & 0 \\
	 Q-Learning  & 0.001  & 0.8  & 0.2 \\
	 Q-Learning  & 0.001  & 0.8  & 0.5 \\
	 Q-Learning  & 0.001  & 0.8  & 0.8 \\
  \hline
\end{tabular}
\caption {Alphas en Qlearning}
\end{table}

\begin{table}[h!]
\center
\begin{tabular}{ | c | c | c | c | }
  \hline
  Agente & $\epsilon$ & $\gamma$ & $\alpha$ \\
  \hline 
 	 Q-Learning  & 0.0001  & 0.01  & 0.7 \\
	 Q-Learning  & 0.0001  & 0.1  & 0.7 \\
	 Q-Learning  & 0.0001  & 0.5  & 0.7 \\
	 Q-Learning  & 0.0001  & 0.9  & 0.7 \\
  \hline
\end{tabular}
\caption {Gammas en Qlearning}
\end{table}


\newpage

\subsection{Resultados}

Los siguientes resultados son en base a corridas en donde los refuerzos eran los siguientes:
\begin{itemize}
\item Refuerzo por pasar = -1
\item Refuerzo por tirar y no golpear a la torre = -30
\item Refuerzo por pegarle a la torre y lograr que se caiga = -5000
\item Refuerzo por tiro exitoso (golpe\'o la torre y se agreg\'o un nuevo piso) = 2000
\end{itemize}

\includegraphics[scale=0.6]{Graficos/estabilidadesQ}
Como se puede ver en este primer resultado, a medida que el piso desde donde arranca a jugar aumenta, la dificultad disminuye, esto es adecuado ya que el p\'endulo que modelamos funciona de esa manera.

\includegraphics[scale=0.6]{Graficos/estabilidadesS}
Con \slambda ocurre algo similar, aunque con una mayor variabilidad, en especial si se juega desde el piso 50. En este resultado podemos observar un comportamiento extran\~o del algoritmo, en el cual parece haberle dado importancia a una acci\'on erronea luego de haber obtenido buenos resultados (ver S50)

\newpage
Recordar que los pr\'oximos resultados se obtuvieron jugando a partir del piso 50 y hasta lograr 20 pisos.

\includegraphics[scale=0.6]{Graficos/QvsS}
El comportamiento de los algoritmos en este caso fue un poco ca\'otico, en especial Sarsa con $\lambda$ = 0.03, en donde se alcanzo el valor optimo durante un tiempo, pero luego volvi\'o a bajar a la mitad. Por otro lado, Q-Learning se mantuvo con muy buenos resultados. 

\includegraphics[scale=0.6]{Graficos/epsilonsQ}
En este experimento, se ve que mientras epsilon es mas chico, funciona mejor (con resultados muy parecidos para epsilons muy chicos). Esto puede deberse a la esencia del problema, el cual parece funcionar bien con algoritmos semi-golosos, en donde un poco de aleatoriedad ayuda, pero en cantidades mas grandes parece perjudicar. Creemos que esto tiene que ver con la forma del problema en donde una vez que se consigue agregar un bloque, conviene seguir prestando atenci\'on al mismo tipo de estados, y no investigar nuevos. 

\includegraphics[scale=0.6]{Graficos/gammasQ}
En este ejemplo, y dados los resultados anteriores (en donde parece que un algoritmo goloso es la mejor soluci\'on) vemos que los cambios en $\gamma$ no afectan al resultado.

\includegraphics[scale=0.6]{Graficos/alphasQ}
Al igual que el ejemplo anterior, el factor $\alpha$  no afecta en gran medida, excepto cuando el 0, lo cual tiene sentido ya que un $\alpha$ tendiendo a cero significa no darle importancia al aprendizaje calculado. 

\subsection{Conclusiones}
Luego de analizar los resultados, llegamos a la conclusi\'on de que resulto f\'acil para el agente implementado usando Q-Lerning encontrar soluciones al problema cuando la estabilidad del edificio ayuda, ya que el problema parece solucionarse de buena manera con algoritmos Golosos. 

Por otro lado, el algoritmo \slambda parece no funcionar muy bien para este tipo de problemas, ademas de demorar mucho m\'as (hasta 10 veces m\'as). 

Algoritmicamente, el desafi\'o mas grande fue modelar un ambiente que modele el juego con algo de realismo. Queda para trabajo futuro, intentar diseñar una interfaz gr\'afica que muestre como se comportan los algoritmos e intentar aplicar otros algoritmos, quiz\'as mas directos para ver como funcionan. 



\newpage

\section{Anexo A}
\subsection{Código de Q-Learning}
\begin{verbatim}
    def run_episode(self):
        state = self.environment.start()
        rewards = 0
        movements = 0
        
        while not (state.has_finished()):
            
            #usando una politica derivada de Q (eps-greedy en este caso)
            action = self.choose_action(state)
            
            new_state, reward = self.environment.make_action(action)
            max_action = self.max_action(new_state)
            key = (state,action)
            self.set_q_value(
                key, 
                (1-self.alpha) * self.q_value((state,action)) + 
                self.alpha * (reward + self.gamma * 
                                       self.q_value((new_state, max_action)))
            )
            
            state = deepcopy(new_state)
            rewards += reward
            movements += 1
        return rewards
\end{verbatim}


\subsection{Código de Sarsa-Lambda}
\begin{verbatim}
    def run_episode(self):
        state = self.environment.start()
        rewards = 0
        movements = 0
        
        #usando una politica derivada de Q (eps-greedy en este caso)
        action = self.choose_action(state)
                
        while not (state.has_finished()):
            new_state, reward = self.environment.make_action(action)
            new_action = self.choose_action(new_state)
            delta = reward + self.gamma * self.q_value((new_state, new_action)) 
                                - self.q_value((state,action))
            
            self.set_e_value((state,action),1.0)
            for k in self.elegibilities.keys():
                self.set_q_value(
                    k, 
                    self.q_value(k) + self.alpha*delta*self.e_value(k)
                )
                
                self.set_e_value(
                    k, 
                    self.e_value(k)*self.gamma*self.lambda_val
                )

            state = deepcopy(new_state)
            action = new_action
            rewards += reward
            movements += 1
        
        return rewards
\end{verbatim}

\end{document}
